package day74;

import java.time.temporal.Temporal;
import java.util.*;
import java.util.jar.Attributes;

public class Solution {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public boolean evaluateTree(TreeNode root) {
        if(root.left == null && root.right == null) {
            return root.val == 1;
        }
        if(root.val == 2) return evaluateTree(root.left) || evaluateTree(root.right);
        if(root.val == 3) return evaluateTree(root.left) && evaluateTree(root.right);
        return false;
    }
    class KthLargest {
        int k;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        public KthLargest(int k, int[] nums) {
            this.k = k;
            for (int x: nums) {
                priorityQueue.offer(x);
            }
        }

        public int add(int val) {
            priorityQueue.offer(val);
            while (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
            return priorityQueue.peek();
        }
    }
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return root;
        mirrorTree(root.left);
        mirrorTree(root.right);
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }
    public boolean checkSymmetricTree(TreeNode root) {
        if(root == null) return true;
        return check(root.left,root.right);
    }
    private boolean check(TreeNode l,TreeNode r) {
        if(l == null && r == null) return true;
        if(l == null || r == null) return false;
        if(l.val != r.val) return false;
        return check(l.left,r.right) && check(l.right,r.left);
    }
    public List<List<Integer>> decorateRecord(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null) return ans;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int t = queue.size();
            List<Integer> list = new ArrayList<>();
            while (t>0) {
                if(queue.peek().left != null) queue.offer(queue.peek().left);
                if(queue.peek().right != null) queue.offer(queue.peek().right);
                list.add(queue.poll().val);
                t--;
            }
            ans.add(list);
        }
        return ans;
    }
    public int findTargetNode(TreeNode root, int cnt) {
        // 第k大的员工编号
        // 二叉搜索树的中序遍历
//        int k = 0;
//        Stack<TreeNode> stack = new Stack<>();
//        while (root != null || !stack.isEmpty()) {
//            while (root != null) {
//                stack.push(root);
//                root = root.right;
//            }
//            root = stack.pop();
//            k++;
//            if(k == cnt) return root.val;
//            root = root.left;
//        }
//        return -1;
        int k = 0;
        while (root != null) {
            if (root.right == null) {
                TreeNode pre = root.right;
                while (pre.left != null && pre.left != root) {
                    pre = pre.left;
                }
                if(pre.left == null) {
                    pre.left = root;
                    root = root.right;
                } else {
                    k++;
                    if(k == cnt) return root.val;
                    root = root.left;
                    pre.left = null;
                }
            } else {
                k++;
                if(k == cnt) return root.val;
                root = root.left;
            }
        }
        return -1;
    }
    public int calculateDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return Math.max(calculateDepth(root.left),calculateDepth(root.right))+1;
    }
//    public boolean isBalanced(TreeNode root) {
//        // 任意两个子树之间的深度差不超过1
//        // 从下往上
//        return check(root) != -1;
//    }
//    private int check(TreeNode root) {
//        if (root == null) return 0;
//        int left = check(root.left);
//        if(left == -1) return -1;
//        int right = check(root.right);
//        if(right == -1) return -1;
//        return Math.abs(left-right)<=1?Math.max(left,right)+1:-1;
//    }
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
////        TreeNode[] pParents = getHeigtList(root,p);
////        TreeNode[] qParents = getHeigtList(root,q);
////        for (int i = Math.min(pParents.length,qParents.length)-1; i > 0; i--) {
////            if(pParents[i] == qParents[i]) return pParents[i];
////        }
////        return null;
////        while (root != null) {
////            if(root.val < p.val && root.val < q.val) {
////                root = root.right;
////            } else if (root.val >p.val && root.val > q.val) {
////                root = root.right;
////            } else {
////                return root;
////            }
////        }
////        return null;
//        if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right,p,q);
//        if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left,p,q);
//        return root;
//    }
    private TreeNode[] getHeigtList(TreeNode root,TreeNode target) {
        List<TreeNode> nodes = new ArrayList<>();
        while (root != null) {
            nodes.add(root);
            if(root.val > target.val) {
                root = root.left;
            } else if (root.val < target.val) {
                root = root.right;
            } else {
                break;
            }
        }
        return nodes.toArray(new TreeNode[nodes.size()]);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        LinkedList<TreeNode> list1 = new LinkedList<>();
//        LinkedList<TreeNode> list2 = new LinkedList<>();
//        getPath(list1,root,p);
//        getPath(list2,root,q);
//        TreeNode ans = root;
//        while (!list1.isEmpty() && !list2.isEmpty()) {
//            if(list1.getFirst() != list2.getFirst()) return ans;
//            ans = list1.removeFirst();
//            list2.removeFirst();
//        }
//        return ans;
        // 假设root是p和q的公共祖先 如果左子节点和右子节点都不是p和q的公共祖先 则root是p和q的最近公共祖先
        //
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left == null) // 左节点没有p和q的公共父节点
            return right;
        if(right == null) // 右节点没有p和q的公共父节点
            return left;
        return root; // 左右节点都不为空说明root就是p和q的公共父亲节点
    }
    private void getPath(LinkedList<TreeNode> path,TreeNode root,TreeNode target) {
//        if(root == null) return;
//        path.addLast(root);
//        if(root == target) return;
//        if(path.getLast() != target) {
//            getPath(path,root.left,target);
//        }
//        if(path.getLast() != target) {
//            getPath(path,root.right,target);
//        }
//        if(path.getLast() != target) {
//            path.removeLast();
//        }
        if(root == null) return;
        path.addLast(root);
        if(root == target) return;
        getPath(path,root.left,target);
        if(path.getLast() != target) {
            getPath(path,root.right,target);
        }
        if(path.getLast() != target) {
            path.removeLast();
        }
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums,0,nums.length-1);
    }
    private TreeNode dfs(int[] nums,int l,int r) {
        if(l>r) return null;
        int mid = (l+r)/2;
        TreeNode ans = new TreeNode(nums[mid]);
        ans.left = dfs(nums,l,mid-1);
        ans.right = dfs(nums,mid+1,r);
        return ans;
    }
    public boolean isBalanced(TreeNode root) {
        return check(root) != -1;
    }
    private int check(TreeNode root) {
        if(root == null) return 0;
        int left = check(root.left);
        if(left == -1) return -1;
        int right = check(root.right);
        if(right == -1) return -1;
        return Math.abs(left-right) <= 1?Math.max(left,right)+1:-1;
    }
    public int climbStairs(int n) {
        int[][] q = {{1, 1}, {1, 0}};
        int[][] res = pow(q, n);
        return res[0][0];
    }
    // 矩阵快速幂

    // 1 1 * f(n)   == f(n)+f(n-1)+f(n) = f(n+1)  f(n)
    // 1 0   f(n-1)
    public int[][] pow(int[][] a,int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }
    // 矩阵乘法
    public int [][] multiply(int[][] a,int[][] b) {
        int[][] c = new int[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                for (int k = 0; k < b[j].length; k++) {
                    c[i][k] += a[i][j] * b[j][k];
                }
            }
        }
        return c;
    }

}

